package com.company.algo.stack.monotonicStack;

import java.util.Comparator;
import java.util.PriorityQueue;

/**
 * https://leetcode-cn.com/problems/trapping-rain-water-ii/
 *es:
 * 给出如下 3x6 的高度图:
 * [
 *   [1,4,3,1,3,2],
 *   [3,2,1,3,2,4],
 *   [2,3,3,2,3,1]
 * ]
 * 返回 4
 * 思路和前面二维一样，对于某个柱子，往周围扩散找4个方向的最短板base
 * res += base - height[i][j]
 * 但是这样如何确定遍历的起点和终点呢？
 *
 * 逆向思考，既然每个位置我无法找到水平面来结算，那是否能找到一个泄水口来结算一批位置呢？
 * 就是能不能找到这么个位置，它四周肯定是以它作为水平面的？
 * 这个好像是可以的，比如说外围一圈，那个最短的地方肯定能结算它四周的位置，因为雨下的足够大，
 * 你不可能会低于这个短板，高于这个短板又会溢出，所以这个结算肯定是正确的。
 * 这样的话，我每次都找外围的短板，然后结算它四周的位置，不断的缩小这个外围不就能把水量算出来了嘛
 * 整个框架基于bfs。
 *
 */
class Location {
    int row, col, height;

    public Location(int row, int col, int height) {
        this.row = row;
        this.col = col;
        this.height = height;
    }
}
public class TrappingRainWater2 {
    int[] d = {1,0,-1, 0, 1};
    public int trapRainWater(int[][] heightMap) {
        int rows = heightMap.length;
        int cols = heightMap[0].length;
        boolean[][] visited = new boolean[rows][cols];

        PriorityQueue<Location> locations = new PriorityQueue<>(Comparator.comparingInt(x -> x.height));
        //构造外围圈
        //第一行和最后一行
        for(int col = 0; col<cols; col++){
            locations.add(new Location(0,col,heightMap[0][col]));
            locations.add(new Location(rows-1,col,heightMap[rows-1][col]));
            visited[0][col] = true;
            visited[rows-1][col] = true;
        }
        //第一列和最后一列
        for(int row = 0; row<rows; row++){
            locations.add(new Location(row,0,heightMap[row][0]));
            locations.add(new Location(row,cols-1,heightMap[row][cols-1]));
            visited[row][0] = true;
            visited[row][cols-1] = true;
        }
        //找到四周的最短板作为start
        int shortSlap = 0;
        int waterAll = 0;
        while(!locations.isEmpty()){
            Location cur = locations.poll();
            shortSlap = Math.max(shortSlap, cur.height);
            //结算短板四周的水量
            int row = cur.row;
            int col = cur.col;
            for(int i=0; i<4; i++){
                int newRow = row + d[i];
                int newCol = col + d[i+1];
                //结算水量，用短板减去这里的地势，差值就是hold住的水
                if(newRow<rows && newRow >= 0 && newCol<cols && newCol>=0 && !visited[newRow][newCol]){
                    waterAll+=Math.max(0, shortSlap-heightMap[newRow][newCol]);
                    visited[newRow][newCol] = true;
                    locations.add(new Location(newRow,newCol,heightMap[newRow][newCol]));
                }
            }
        }
        return waterAll;
    }
}
